package leetcode101.binary_search;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code4
 * @Description 154. Find Minimum in Rotated Sorted Array II
 * Suppose an array of length n sorted in ascending order is rotated between 1 and n times.
 * For example, the array nums = [0,1,4,4,5,6,7] might become:
 *
 * [4,5,6,7,0,1,4] if it was rotated 4 times.
 * [0,1,4,4,5,6,7] if it was rotated 7 times.
 * Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array
 * [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
 *
 * Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.
 *
 *
 * Example 1:
 *
 * Input: nums = [1,3,5]
 * Output: 1
 * Example 2:
 *
 * Input: nums = [2,2,2,0,1]
 * Output: 0
 *
 * Constraints:
 *
 * n == nums.length
 * 1 <= n <= 5000
 * -5000 <= nums[i] <= 5000
 * nums is sorted and rotated between 1 and n times.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-28 10:36
 */
public class Code4 {
    public static void main(String[] args) {

    }

    public static int findMin(int[] nums) {
        int low = 0, high = nums.length - 1, mid;
        while (low < high) {
            mid = low + ((high - low) >> 1);
            if (nums[mid] < nums[high]) {
                high = mid;
            } else if (nums[mid] > nums[high]) {
                low = mid + 1;
            } else {
                high--;
            }
        }
        return nums[low];
    }
}
/*
二分查找对于旋转数组的最小值同样可以进行查找
要注意的是left和right指针之间，包括两个指针所指的元素都可能是要查找的元素
旋转数组的最小值一定出现在分界点，所以对旋转数组中最小值的查找的本质可以归结为对分界点的查找
那么如何对分界点进行查找呢？
我们当然可以暴力的解决：
    只要找到某一个元素大于后面的元素则找到了分界点，如果遍历到了最后都没找到，说明数组是有序的或者是元素都一样
    这时我们返回arr[0]即可

那么我们可不可以对旋转数组的分界点进行二分查找呢？
    当然可以，我们可以这么想：
    旋转数组其实是由两个有序的数组组成的
    对于没有重复的旋转数组来说：
        如果arr[mid] < arr[right] 则说明mid右半边数组是有序的，分界点在mid的左边 将 right=mid, 因为arr[mid]有可能是最小值
        如果arr[mid] > arr[right] 则说明mid左半边数组是有序的，分界点在mid的右边 令 left = mid + 1 因为arr[mid]不可能是最小值
    对于有重复元素的旋转数组来说：
        如果出现了arr[mid] == arr[right] 则将 right 左移，继续缩小范围
 */